package com.fmm.hard;

import java.util.ArrayList;
import java.util.List;

public class NQueen {

    /**
     * @param n 代表 n * n 的棋盘上有 n 个皇后需要放置
     * @return 所有可能得解
     * */
    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        // 列占用情况，true 表示某一列已经被占用
        boolean[] column = new boolean[n];
        // "/" 方向，i + j 作为索引
        boolean[] lSlash = new boolean[2 * n - 1];
        // "\" 方向，i - j + n - 1 作为索引
        boolean[] rSlash = new boolean[2 * n - 1];
        tryPut(column, lSlash, rSlash, n, 0, new ArrayList<>(), result);
        return result;
    }

    /**
     * @param column 列占用情况
     * @param lSlash "/" 方向占用情况
     * @param rSlash "\" 方向占用情况
     * @param n 棋盘大小
     * @param i 当前行的索引
     * @param snapShot 快照，里面的数字元素表示第索引行的第几列放了皇后 Q，当方案成功后，把快照加入结果集中
     * @param result 结果集，用来存放最终结果
     * */
    private static void tryPut(
            boolean[] column, boolean[] lSlash, boolean[] rSlash, int n, int i,
            List<Integer> snapShot, List<List<String>> result) {
        // 当前行已经超出了棋盘大小，说明所有 Q 都已经成功放置，这时，把快照信息加入结果集
        if (i > n - 1) {
            List<String> plan = new ArrayList<>();
            for (Integer col : snapShot) {
                plan.add(new StringBuilder(".".repeat(n)).replace(col, col + 1, "Q").toString());
            }
            result.add(plan);
            return;
        }
        // 对于当前行，尝试在所有列上放置皇后，j 为列索引
        for (int j = 0; j < n; j++) {
            // 如果纵向，两个斜向都满足，则尝试放置
            if (!column[j] && !lSlash[i + j] && !rSlash[i - j + n - 1]) {
                // 把放置结果加入快照
                snapShot.add(j);
                // 更新列、两个斜向的占用状态
                column[j] = true;
                lSlash[i + j] = true;
                rSlash[i - j + n - 1] = true;
                // 递归尝试下一行
                tryPut(column, lSlash, rSlash, n, i + 1, snapShot, result);
                // 恢复列、两个斜向的占用状态
                column[j] = false;
                lSlash[i + j] = false;
                rSlash[i - j + n - 1] = false;
                // 恢复快照
                snapShot.remove(snapShot.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(solveNQueens(8));
    }
}
